package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class PrintBinaryTree {
	
	//方法一：BFS，我写的
    public List<List<String>> printTree(TreeNode root) {
        
    	int height = getHeight(root);
    	int m = height + 1, n = (int)Math.pow(2, m) - 1;
    	
    	List<String> emptyRow = new ArrayList<>(n);
    	for(int i = 0; i < n; i++)
    		emptyRow.add("");
    	
    	List<List<String>> result = new ArrayList<>();
    	
    	LinkedList<Object> queue = new LinkedList<>();
    	queue.offer(root);
    	queue.offer(new int[] {0, (n - 1) / 2});
    	
    	while(!queue.isEmpty()) {
    		
    		List<String> newRow = new ArrayList<>(emptyRow);
    		for(int size = queue.size(); size > 0; size -= 2) {
    			
    			TreeNode node = (TreeNode)queue.poll();
    			int[] index = (int[])queue.poll();
    			int r = index[0], c = index[1];
    			
    			newRow.set(c, String.valueOf(node.val));
    			
    			if(node.left != null) {
    				queue.offer(node.left);
    				queue.offer(new int[] {r + 1, c - (int)Math.pow(2, height - r - 1)});
    			}
    				
    			if(node.right != null) {
    				queue.offer(node.right);
    				queue.offer(new int[] {r + 1, c + (int)Math.pow(2, height - r - 1)});
    			}
    		}
    		result.add(newRow);
    	}
    	
    	return result;
    }
    
    
    public int getHeight(TreeNode root) {
    	if(root == null)
    		return 0;
    	
    	int temp = 0;
    	if(root.left != null || root.right != null)
    		temp = 1;
    	
    	return temp + Math.max(getHeight(root.left), getHeight(root.right));
    }
    
    
    //方法二：别人写的，DFS（或二叉树的前序遍历）
    public List<List<String>> printTree2(TreeNode root) {
        List<List<String>> res = new LinkedList<>();
        int height = root == null ? 1 : getHeight2(root);
        int rows = height, columns = (int) (Math.pow(2, height) - 1);
        List<String> row = new ArrayList<>();
        for(int i = 0; i < columns; i++)  
        	row.add("");
        
        for(int i = 0; i < rows; i++)  
        	res.add(new ArrayList<>(row));
        populateRes(root, res, 0, rows, 0, columns - 1);
        return res;
    }

    public void populateRes(TreeNode root, List<List<String>> res, int nRow, int totalRows, int left, int right) {
        if (nRow == totalRows || root == null) return;
        int mid = left + (right - left) / 2;
        res.get(nRow).set(mid, Integer.toString(root.val));
        populateRes(root.left, res, nRow + 1, totalRows, left, mid - 1);
        populateRes(root.right, res, nRow + 1, totalRows, mid + 1, right);
    }

    public int getHeight2(TreeNode root) {
         if (root == null) return 0;
         return 1 + Math.max(getHeight2(root.left), getHeight2(root.right));
    }
    
}
